struct Node* copyRandomList(struct Node* head) {
    //拷贝结点到原结点后面
    struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;


        copy->next=cur->next;
        cur->next=copy;
        
        cur=copy->next;
    }


    //处理random指针
    cur=head;
    while(cur)
    {
         struct Node* copy=cur->next;
         if(cur->random==NULL)
         {
             copy->random=NULL;
         }
         else
         {
             copy->random=cur->random->next;
         }


         cur=copy->next;
    }
    //分离拷贝链表和复原原链表
     struct Node* newhead=NULL,*tail=NULL;
     cur=head;
     while(cur)
     {
         struct Node* copy=cur->next;
         struct Node* next=copy->next;


         if(tail==NULL)
         {
             tail=newhead=copy;
         }
         else
         {
             tail->next=copy;
             tail=tail->next;
         }
         cur->next=next;


         cur=next;
     }


     return newhead;
}